package com.example.algorithm.insertionsort;

/**
 * 插入排序：
 * 每次从剩余的数据中获取第一个元素，然后在前面已经排好序的元素中寻找其适合插入的位置，将其插入
 */
public class InsertionSort {

    private InsertionSort() {
    }

    /**
     * 循环不变量分析：
     * arr[0,i) 已经排好序；
     * arr[i,n) 未排序
     * 维护循环不变量：
     * 把 arr[i] 放到合适的位置
     *
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int n = i; n >= 1; n--) {
                if (arr[n].compareTo(arr[n - 1]) < 0) {
                    swap(arr, n, n - 1);
                } else {
                    break;
                }
            }
        }
    }

    /**
     * 优化点：
     * 使用平移，减少交换的次数，
     *
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            E tmp = arr[i];
            int n;
            for (n = i; n >= 1; n--) {
                if (tmp.compareTo(arr[n - 1]) < 0) {
                    arr[n] = arr[n - 1];
                }
            }
            arr[n] = tmp;
        }
    }

    /**
     * 对于给定数组的 [l,r] 区间内的元素进行排序
     *
     * @param arr
     * @param l
     * @param r
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        for (int i = l; i <= r; i++) {
            E tmp = arr[i];
            int n;
            for (n = i; n >= l + 1; n--) {
                if (tmp.compareTo(arr[n - 1]) < 0) {
                    arr[n] = arr[n - 1];
                }
            }
            arr[n] = tmp;
        }
    }

    private static <E> void swap(E[] arr, int idx1, int idx2) {
        E tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
}
